package oj.oj_niuke_链表中倒数第k个结点;

import oj.ListNode;

/**
 * 双指针法：一前一后同步进行 判断->前->后
 */
//时间复杂度：O(n)
//空间复杂度：O(1)
public class Solution2 {
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode forward=head;

        // 先让 forward 往前跳 k 步
        for (int i = 0; i < k; i++) {
            if(forward==null){
                return null;// 说明 链表长度不够 k 个，返回 null
            }
            forward=forward.next;
        }
        // forward 可能是 null
        ListNode backward=head;
        while(forward!=null){
            forward=forward.next;
            backward=backward.next;
        }
        // backward 指向倒数第 k 个结点
        return backward;
    }
}
